package com.demo.leetcode;

public class leetcode05 {
    /**
     * 给定一个字符串 s ，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
     * 示例 1：
     * 输入: "babad"
     * 输出: "bab"
     * 注意: "aba"也是一个有效答案。
     * 示例 2：
     * 输入: "cbbd"
     * 输出: "bb"
     */
    public static String longestStr(String str) {
        if (str == null || str.length() <= 1) {
            return str;
        }
        String result = "";
        for (int i = 0; i < str.length(); i++) {
            int t1 = around(str, i, i);
            int t2 = around(str, i, i + 1);
            int max = Math.max(t1, t2);
            if (max > result.length()) {
                result = str.substring(i - (max - 1) / 2, i + max / 2 + 1);
            }
        }
        return result;
    }

    //获取某个字符所在的最长回文长度
    private static int around(String str, int left, int right) {
        while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    public static void main(String[] args) {
        String str = longestStr("dbbabbdd");
        System.out.println(str);
    }


}
